import java.util.ArrayList;

public class Apl {

	private static ArrayList<InsertionSort> sorters = new ArrayList<InsertionSort>();
	private final int START_UP_THREADS = 16;
	private final int DEFAULT_LIST_SIZE = 10000;

	public static void main(String[] args) {
		Apl apl = new Apl();
		apl.testRun(2);
	}

	public void testRun(int listSizeFactor) {
		for (int currentListSizeFactor = 0; currentListSizeFactor <= listSizeFactor; currentListSizeFactor++) {
			int amountOfThreads = START_UP_THREADS;
			int totalSortingTime = 0;
			int efficientSortingTime = 0;
			boolean isEfficient = false;
			int listSize = DEFAULT_LIST_SIZE
					* (int) (Math.pow(10, currentListSizeFactor));
			while (!isEfficient) {
				totalSortingTime = (int) run(listSize, amountOfThreads);
				System.out.println("Average sorting time for "
						+ amountOfThreads + " thread(s) with a list size of ["
						+ listSize + "] : " + totalSortingTime + "ms");
				if (amountOfThreads == START_UP_THREADS
						|| totalSortingTime <= efficientSortingTime) {
					efficientSortingTime = totalSortingTime;
					amountOfThreads *= 2;
				} else {
					amountOfThreads /= 2;
					isEfficient = true;
					System.out.println("on a list of " + listSize
							+ " the most efficient is to use "
							+ amountOfThreads + " threads" + "\n");
				}
			}
		}
	}

	private double run(int listSize, int maxThreads) {
		int[] randomArray = ArrayGenerator.getArray(listSize);
		Data data = new Data(randomArray);
		ArrayList<Thread> threads = new ArrayList<Thread>();
		long currentTime = System.nanoTime();
		double sortTime;
		threads = initThreads(data, listSize, maxThreads);
		for (Thread thread : threads) {
			thread.start();
		}
		try {
			for (Thread thread : threads) {
				thread.join();
			}
		} catch (InterruptedException e) {

		}
		// Merge returns an ArrayList which it received from the threads after the array has been merged.
		merge(listSize);
		//ArrayList<Integer> finalList = merge(listSize);
		sortTime = (System.nanoTime() - currentTime) / new Double(1000000);
		return sortTime;
	}

	private ArrayList<Thread> initThreads(Data data, int listSize,
			int maxThreads) {
		ArrayList<Thread> threads = new ArrayList<Thread>();
		int start = 0;
		int end = -1;
		int chunk = 0;
		for (int currentThread = 1; currentThread <= maxThreads; currentThread++) {
			chunk = determineChunk(listSize, maxThreads, currentThread);
			start = end + 1;
			end += chunk;
			InsertionSort iSort = new InsertionSort(data, start, end);
			sorters.add(iSort);
			Thread thread = new Thread(iSort);
			threads.add(thread);
		}
		return threads;
	}

	private int determineChunk(int randomArraySize, int threadAmount,
			int currentThread) {
		int remainder = randomArraySize % threadAmount;
		int threadsLeft = threadAmount - currentThread + 1;
		if (threadsLeft > remainder || remainder == 0) {
			return randomArraySize / threadAmount;
		}
		return randomArraySize / threadAmount + 1;
	}

	private ArrayList<Integer> merge(int listSize) {
		int numbersLeft = listSize;
		int maximumNumber = listSize;
		ArrayList<Integer> finalList = new ArrayList<Integer>();
		ArrayList<Integer> listWithSmallestNumber = new ArrayList<Integer>();
		ArrayList<ArrayList<Integer>> allLists = new ArrayList<ArrayList<Integer>>();
		for (InsertionSort sorter : sorters) {
			allLists.add(sorter.getList());
		}
		while (numbersLeft > 0) {
			int smallestNumber = maximumNumber;
			for (ArrayList<Integer> sortedList : allLists) {
				if (!sortedList.isEmpty()) {
					if (sortedList.get(0) <= smallestNumber) {
						smallestNumber = sortedList.get(0);
						listWithSmallestNumber = sortedList;
					}
				}
			}
			finalList.add(smallestNumber);
			listWithSmallestNumber.remove(0);
			numbersLeft--;
		}
		sorters.clear();
		return finalList;
	}
}
